(a) Field of the Invention
The present invention relates to a system for decoding compressed data. The system of the present invention is used for decoding compressed data of a facsimile data transmission.
(b) Background of the Prior Art
In general, data compression has been used for speeding up facsimile data transmission.
A prior art technique of coding and decoding compressed data using correlationship in data of adjacent scan lines is illustrated in FIGS. 1 and 2A through 2E. The prior art system for decoding compressed data is illustrated in FIG. 1. The system of FIG. 1 comprises a memory 1 for storing the compressed data, a circuit 2 for equalizing bit lengths of codes and a shift register 8 for a preceding scan line. The sytem also includes a circuit 46 for detecting color change elements, a circuit 47 for generating shift pulses and a circuit 48 for counting addresses on the preceding scan line a. Additionally included is a circuit 64 for addition/substraction and a circuit 65 for addition. The systems further includes a memory 76 for the address of a color change element in question, a circuit 72 for restoring the picture elements for a current scan line, a circuit 74 for counting addresses on the current scan line, a device 73 for reproducing the picture and a memory 75 for a current scan line. The circuit 2 for equalizing the bit lengths of codes produces data D3 for the selection of a reference correlated color change element, data D11 for a relative distance between the reference correlated color change element and the color change element in question or needed and data D12 for a distance between the last preceding color change element and the independent color change element in question.
The procedures which are carried out by the system of FIG. 1 will be explained with reference to color element patterns of pictures illustrated in FIGS. 2A through 2E. In FIGS. 2A through 2E patterns of the pictures along the current scan line (a) and the preceding scan line (b) are illustrated. Line scans are carried out horizontally from the left side to the right side, while line-by-line scans are carried out vertically from the top side to the bottom side. Hatched picture elements represent black elements, while non-hatched picture elements represent white elements. P.sub.1, P.sub.2, P.sub.3, P.sub.x and Q are the color change elements. Color changes from white to black at P.sub.1, P.sub.2, P.sub.3 and Q, while color changes from black to white at P.sub.x. The nature of these color change elements are as follows.
(1) Q is the color change element in question or needed color change element on the current scan line.
(2) P.sub.x is the last preceding color change element on the current scan line with respect to Q.
(3) P.sub.1 is a color change element on the preceding scan line the type of which color change is the same as that of the type of color change of the color change element in question. In FIGS. 2A through 2E, for example, the color changes from white to black both at Q and P.sub.1.
(4) P.sub.2 is the next color change element on the preceding scan line the type of which color change is the same as that of the color change of P.sub.1.
There are two kinds of color change elements in question Q in FIGS. 2A through 2E. That is, the color change elements Q in FIGS. 2A, 2B and 2C are "correlated" color change elements, while the color change elements Q in FIGS. 2D and 2E are "independent" color change elements.
The difference between a correlated color change element and an independent color change element is as follows. That is, if there is a run of picture elements, i.e. the continuous sequence of picture elements, which have the same color as the color of the color change element in question on the current scan line, existing on the preceding scan line which overlaps the run of picture elements starting with the color change element in question on the current scan line and does not overlap the immediately preceding run of picture elements, which have the same color as the color of the color change element in question, existing on the current scan line, such color change element in question is called a "correlated" color change element. While, if there is a run of picture elements, which have the same color as the color of the color change element in question on the current scan line, on existing the preceding scan line which does not overlap the run of picture elements starting with the color change element in question on the current scan line, or if there is a run of picture elements on the preceding scan line, which have the same color as the color of the color change element in question on the current scan line which overlaps both the run of picture elements starting with the color change element in question and the preceding run of picture elements which have the same color as the color of the color change element in question on the current scan line, such a color change element in question is called an "independent" color change element.
The address of a color change element in question is determined by the address of the reference color change element and the distance between the reference color change element and the color change element in question.
In FIGS. 2A, 2B and 2C, the address data for the color change element Q in question are as follows.
For Q of FIG. 2A . . . (1, +1)
For Q of FIG. 2B . . . (1, -2)
For Q of FIG. 2C . . . (2, -1)
The first numerals "1", "1" and "2" in the parentheses are position data and indicate that the reference color change elements on the preceding scan line are P.sub.1 (FIG. 2A), P.sub.1 (FIG. 2B) and P.sub.2 (FIG. 2C), respectively. The second numerals "+1", "-2" and "+1" in the parentheses indicate that the relative displacement of the color change element in question from the reference color change element are one picture element to the right (FIG. 2A), two picture element to the left (FIG. 2B) and one picture element to the right (FIG. 2C), respectively.
In FIGS. 2D and 2E, the address data for the color change element Q in question are determined by the address of the reference color change element P.sub.X and the distance between the reference color change element P.sub.X and the color change element Q in the question. The adjacent preceding color change element on the current scan line is selected as the reference color change element for the independent color change element Q in question as illustrated in FIGS. 2D and 2E. If no preceding color change element exists on the current scan line, the first picture element on the current scan line is selected as the reference color change element.
The prior art technique of decoding compressed data on the basis of the patterns illustrated in FIGS. 2A through 2E is carried out by the prior art system for decoding compressed data illustrated in FIG. 1. Data for the preceding scan line stored in the shift register 8 are shifted by the shift pulses supplied from the circuit 47 for generating shift pulses. Addresses of color change elements are counted by the circuit 48 for counting addresses on the preceding scan line. Circuit 48 receives signals from the circuit 47 for generating shift pulses which receives signals from the circuit 46 for detecting color change elements. Data for the correlated color change element in question is calculated in the circuit 64 for addition/subtraction, which circuit 64 receives the data from the circuit 48 and the data D11 from the circuit 2, and stored in the resister 76 for the address of a color change element in question. The data of an independent color change element in question is calculated in the circuit 65 for addition, which circuit 65 receives the data from the circuit 74 for counting addresses on the current scan line and the data D12 from the circuit 2, and stored in the register 76. The data stored in the register 76 is written into the circuit 72 for restoring the data for picture elements for a current scan line. The data for picture elements in the circuit 72 is supplied to and stored in the memory 75 for a current scan line. The data for picture elements stored in the memory 75 for a current scan line is transmitted to the shift register 8 as the data for the picture elements of the next preceding scan line.
However, in the prior art system of FIG. 1, a predetermined length of time is always required for shifting the data for all of the picture elements of a preceding scan line because the shift register 8 stores the data for all of the picture elements of a preceding scan line. Also, the prior art system of FIG. 1 requires shift circuits and counter circuits for the shift register 8. Accordingly, the prior art system of FIG. 1 is disadvantageous because a high speed decoding operation cannot be attained and the construction of the devices of the system is complicated.
The above described prior art system is disclosed in, for example, Japanese Patent Application Laid-open No. 52-58406.
The present invention is directed to obviating the above described disadvantage in the prior art system.